#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 105. 从前序与中序遍历序列构造二叉树.py
@time: 2022/1/16 14:06
@desc: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
> 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

@解题思路：
    1. 递归构造
    2. Ot(n), Os(n)
'''

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        def build(pre_left, pre_right, in_left, in_right):
            """
            :type pre_left: int 前序左边界
            :type pre_right: int 前序右边界
            :type in_left: int 中序左边界
            :type in_right: int 中序右边界
            """
            if pre_left>pre_right: return None

            pre_root = pre_left
            # 找到根节点在中序遍历的位置
            in_root = index[preorder[pre_root]]

            # 根节点
            root = TreeNode(preorder[pre_root])

            # 计算左子树的元素个数
            left_size = in_root - in_left

            # 递归构造左子树
            root.left = build(pre_left+1, pre_left+left_size, in_left, in_root-1)

            # 递归构造右子树
            root.right = build(pre_left+left_size+1, pre_right, in_root+1, in_right)

            return root


        n = len(preorder)

        # 构建inorder快速查找的哈希表
        index = { ele: i for i, ele in enumerate(inorder)}
        return build(0, n-1, 0, n-1)

if __name__ == '__main__':
    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    res = Solution().buildTree(preorder, inorder)
